All Questions
4 questions
4votes
2answers
171views
Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?
It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by ...
4votes
1answer
931views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions For any automaton $X$, let $L(X)$ denote the language recognized by $X$. For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$. ...
- 5,177
6votes
0answers
792views
Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability
A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we ...
14votes
1answer
677views
Minimizing residual finite state automata
Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular ...
- 10.3k
